package demo.practice.linklist;


import java.util.Stack;

public class P173 {


}


class BSTIterator {

    Stack<Integer> data = new Stack<>();

    public BSTIterator(TreeNode root) {
        midEach(root);
    }

    private void midEach(TreeNode root) {
        if (root == null)
            return;

        if (root.right != null)
            midEach(root.right);
        data.push(root.val);


        if (root.left != null)
            midEach(root.left);
    }

    public int next() {
        if (hasNext())
            return data.pop();
        return -1;
    }

    public boolean hasNext() {
        return data.size() > 0;
    }
}